#include "../tools.h"


class Solution {
public:
    string longestPalindrome(string s) {
        if(s == "") return "";
        if(s.size() == 1) return s;
        if(s.size() == 2 && s[0] == s[1]) return s;
        if(s.size() == 2 && s[0] != s[1]) return s.substr(0, 1);

        int size = s.size();
        bool dp[1010][1010] = {false};
        int maxlen = 1, maxleft = 0, maxright = 0;
        for(int i = 0, j = 1; i <= size - 2; ++i){
            j = i + 1;
            dp[i][i] = true;
            if(s[i] == s[j]){
                dp[i][j] = true;
                maxlen = 2;
                maxleft = i;
                maxright = j;
            }
        }
        dp[size - 1][size - 1] = true;

        for(int len = 3; len <= size; ++len){
            for(int left = 0, right = left + len - 1; right <= size - 1; ++left){
                right = left + len - 1;
                dp[left][right] = (s[left] == s[right] && dp[left + 1][right - 1]);

                if(dp[left][right] && len > maxlen){
                    maxleft = left;
                    maxright = right;
                }
            }
        }

        return s.substr(maxleft, maxright - maxleft + 1);
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    string str = "ccc";

    cout << sol.longestPalindrome(str) << endl;

    return 0;
}
